﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_27 : BaseProblem
    {
        private List<long> _primes = new List<long>();
        private long _maxPrime = 2;

        public override object GetResult()
        {
            const long maxA = 1000;
            const long maxB = 1000;

            long resN = 0;
            long res = 0;
            for (var a = -maxA+1; a < maxA; a++)
            {
                for (var b = -maxB+1; b < maxB; b++)
                {
                    var n = 0;
                    while (true)
                    {
                        if (!IsPrime(GetValue(n, a, b))) break;
                        n++;
                    }
                    n--;
                    if (resN >= n) continue;
                    resN = n;
                    res = a*b;
                }
            }
            return res;
        }

        private static long GetValue(long n, long a, long b)
        {
            return n*n + a*n + b;
        }

        private bool IsPrime(long value)
        {
            value = Math.Abs(value);
            if (_primes.Count == 0) _primes.Add(2);
            long mid = (long)Math.Sqrt(value);
            
            foreach (var l in _primes)
            {
                if (l > mid) return true;
                if (value % l == 0) return false;
            }
            
            for (var l = _maxPrime + 1; l <= mid; l++ )
            {
                bool _isPrime = true;
                foreach (var _prime in _primes)
                {
                    if (l%_prime == 0)
                    {
                        _isPrime = false;
                        break;
                    }
                }
                if (_isPrime)
                {
                    _primes.Add(l);
                    if (value % l == 0)
                    {
                        _maxPrime = l;
                        return false;
                    }
                }
            }
            _maxPrime = mid;
            return true;
        }

        public override string Problem
        {
            get
            {
                return @"Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n²  79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.

Considering quadratics of the form:

n² + an + b, where |a|  1000 and |b|  1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |4| = 4
Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return -59231;
            }
        }

    }
}
